package com.yang.Dp;

/**
 * @Author: yang
 * @Description: 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
 *              该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
 * @Date: Created in 15:55 2022/8/9
 * @Modified By:
 */


// 动态规划五部曲
    // 1.确定dp含义 根据斐波那契定义我们可以规定 dp[i] = 第i个数的值
    // 2.确定递推公式 题中已经给出 dp[i] = dp[i - 1]+ dp[i - 2]
    // 3.初始化数组 dp[0] = 0, dp[1] = 1;
    // 4.确定遍历顺序 因为 dp[i] = dp[i - 1]+ dp[i - 2] 后一个数据依赖前两个数据所以从前往后遍历
    // 5.距离推导dp数组
    // 当n = 6 时  f(6) = 0 1 1 2 3 5 8
public class LeetCode59 {
    public static void main(String[] args) {
        System.out.println(fib(8));
    }

    static public int fib(int n) {
        // dp数组大小为 n+1 因为包含了 n=0的情况
        int dp[] = new int[n + 1];
        if(n <= 1){
            return n;
        }
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return  dp[n];
    }
}
